package multithreaddatastructure;

import java.util.HashMap;

public class LRUCache<K, T> {
    class LRUCacheEntry {
        K key;
        T data;
        LRUCacheEntry next;
        LRUCacheEntry prev;
    }

    private LRUCacheEntry head;
    private LRUCacheEntry tail;

    private HashMap<K, LRUCacheEntry> cacheMap;

    public LRUCache(int size) {
        init(size);
    }

    public T get(K key) {
        LRUCacheEntry entry = cacheMap.get(key);
        if (entry != null) {
            detach(entry);
            attach(entry);
            return entry.data;
        }
        return null;
    }

    public void put(K key, T data) {
        LRUCacheEntry entry = cacheMap.get(key);
        if (entry == null) {
            entry = tail;
            detach(entry);
            cacheMap.remove(entry.key);
            entry.key = key;
            cacheMap.put(key, entry);
        } else {
            detach(entry);
        }
        entry.data = data;
        attach(entry);
    }

    private void init(int size) {
        head = new LRUCacheEntry();// dummy head
        tail = head;
        for (int i = 0; i < size; ++i) {
            tail.next = new LRUCacheEntry();
            tail.next.prev = tail;
            tail = tail.next;
        }
        tail.next = head;
        head.prev = tail;
        cacheMap = new HashMap<K, LRUCacheEntry>();
    }

    private void detach(LRUCacheEntry entry) {
        entry.prev.next = entry.next;
        entry.next.prev = entry.prev;
        if (entry == tail)
            tail = entry.prev;
    }

    private void attach(LRUCacheEntry entry) {
        head.next.prev = entry;
        entry.next = head.next;
        head.next = entry;
        entry.prev = head;
        if (head == tail)
            tail = entry;
    }

    void debug() {
        int cnt = 0;
        LRUCacheEntry cur = head.next;
        while (cur != head) {
            cnt++;
            System.out.println(cur.key + " " + cur.data);
            cur = cur.next;
        }
        System.out.println("tot: " + cnt + " " + cacheMap.size());
    }

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = new LRUCache<Integer, Integer>(1);
        for (int i = 0; i < 10; ++i) {
            cache.put(i, i);
            cache.debug();
        }
    }

}
